import java.util.HashMap;
import java.util.Map;

public class Solution70 {

    public static void main(String[] args) {
        System.out.println(climbStairs(45));
    }
    public static int climbStairs(int n) {
        Map<Integer, Integer> map=new HashMap<Integer,Integer>();
        if(n==1) return 1;
        if(n==2) return 2;
        if(map.get(n)!=null){
            return map.get(n);
        }else{
            int m= climbStairs(n-1)+climbStairs(n-2);
            map.put(n,m);
        }
        return map.get(n);


    }

}
